class Solution {
public:
    int wardrobeFinishing(int m, int n, int cnt) {
        vector<vector<bool>>visited(m,vector<bool>(n,0));
        return dfs(0,0,visited,m,n,cnt);
    }

private:
    int dfs(int i,int j,vector<vector<bool>>&visited,int m,int n,int cnt)
    {
        if(i>=m||j>=n||visited[i][j]||bitSum(i)+bitSum(j)>cnt)return 0;
        visited[i][j]=true;
        return 1+dfs(i,j+1,visited,m,n,cnt)+dfs(i+1,j,visited,m,n,cnt);//向右向下
    }

    int bitSum(int n)
    {
        int sum=0;
        while(n)
        {
            sum+=n%10;
            n/=10;
        }
        return sum;
    }
};